// 1314. 矩阵区域和

function matrixBlockSum(mat: number[][], K: number): number[][] {
    const row = mat.length
    if(row==0) return []
    const col = mat[0].length
    let pre = new Array(row+1).fill(0).map(e=>new Array(col+1).fill(0))
    let ans = new Array(row).fill(0).map(e=>new Array(col).fill(0))

    for(let i=1;i<=row;i++){
        let sum=0
        for(let j=1;j<=col;j++){
            sum+=mat[i-1][j-1]
            if(i==0){
                pre[i][j] = sum
            }else{
                pre[i][j] = sum + pre[i-1][j]
            }
        }
    }

    for(let i=0;i<row;i++){
        let rMin = i-K<0 ? 0 : i-K
        let rMax = i+K+1>row? row :i+K+1
        for(let j=0;j<col;j++){
            let cMin = j-K<0 ? 0 : j-K
            let cMax = j+K+1>col? col :j+K+1
            ans[i][j] = pre[rMax][cMax] - pre[rMax][cMin] - pre[rMin][cMax] + pre[rMin][cMin]
        }
    }
    return ans
};